算法导论笔记-疑问篇之找中序遍历下x结点的后继

titer1 2012-08-17 08:33:12



//查找中序遍历下x结点的后继，后继是大于key[x]的最小的结点  

node *Tree_Successor(node *x)  

{  

    //如果有右孩子  

    if(x->right != NULL)  

        //右子树中的最小值  

        return Tree_Minimum(x->right);  

    //如果x的右子树为空且x有后继y，那么y是x的最低祖先结点，且y的左儿子也是  

    node *y = x->p;  

    while(y != NULL && x == y->right)  

    {  

        x = y;  

        y = y->p;  

    }  

    return y;  

}

想问一下：代码中 while(y != NULL && x == y->right) 为什么加上 x == y->right
第二问书上说：如果求的节点没有有字数，那么后继的最低的祖先。
这里最低如何理解？

...全文

153 4 打赏收藏转发到动态举报

写回复

用AI写文章

4 条回复

切换为时间正序

请发表友善的回复…

发表回复

titer1 2012-08-18

打赏
举报

我把相关想法放到这里

http://www.cnblogs.com/titer1/archive/2012/08/18/2645317.html

titer1 2012-08-18

打赏
举报

今天看了代码

设想了三个情景相通了，谢谢tragedyhomeland

titer1 2012-08-18

打赏
举报

来个左右对比，来理解
二叉查找树，求前驱



//查找二叉查找树中节点x的前驱节点，返回指向该节点的指针 

//在查找过程中，如果节点x左子树不为空，那么返回左子树的最大节点即可 

//如果节点x的左子树为空，那么前驱节点为x的某一个祖先节点的父节点，而且该祖先节点是作为其父节点的右儿子 

Tree tree_predecessor(Tree x) 

{ 

if (x->left_child != null) 

return tree_maxmum(x->left_child); 



Tree y = x->parent; 

while (y != NULL && x == y->left_child) 

{ 

x = y; 

y = y->parent; 

} 

return y; 

}

tragedyhomeland 2012-08-17

打赏
举报

1.因为当x!=y->right时！即x=y->left时.y结点就是X结点的后继，所以不用循环！当x=y->right时说明X的后继是Y结点的父结点。所以需要循环！

2.如果x的右子树为空且x有后继y，那么y是x的最低祖先结点，且y的左儿子也是。意思就是说如果X右子树为空，且有后继，说明X的后继肯定是X的父节点，或者是X父节点的父节点，简洁的说就是那么y是x的最低祖先结点。

楼主最好用笔画画图，分清楚说明是中序遍历。中序遍历规则是：左孩子，结点，右孩子。